//
// Created by DengLibin on 2018/12/16 0016.
//

/** 汉诺塔问题：
如果是一个盘子
直接将A柱子上的盘子 从A移到C
否则
先A柱子上的n-1个盘子借助C移到B
再将A柱子上的最后一个盘子从A移到C
然后将B柱子上的n-1个盘子借助A移到C

时间复杂度2^n
*/
#include <iostream>
using namespace std;

int num = 0;//移动次数

//n个盘子 三个柱子 a,b,c
void han_nuo_fun(int n, char a, char b, char c)
{
    if (n == 1) //只有一个盘子
    {
        cout << "将编号为1的盘子从" << a << "移到" << c << endl;
    }
    else
    {
        //先A柱子上的n-1个盘子借助C移到B
        han_nuo_fun(n - 1, a, c, b);
        //再将A柱子上的最后一个盘子从A移到C
        cout << "将编号为" << n << "的盘子从" << a << "移到" << c << endl;
        //然后将B柱子上的n-1个盘子借助A移到C
        han_nuo_fun(n-1,b,a,c);
    }

    num++;
}

int main38(int argc, char* argv[])
{
    han_nuo_fun(9,'A','B','C');
    cout << "移动次数:" << num << endl;
    return 0;
}